package com.cuz.daileetcode.utils;

import java.util.Arrays;
import java.util.Optional;

/***
 * 马拉车算法
 */
public class Manacher {

    private final static char SPECIAL_CHAR = '#';

    /***
     * 使用 特殊字符 分割字符 生成数组
     * 此步骤可以让最长回文子串的求解忽略奇数偶数的判断
     * @param sourceStr 原字符
     * @return char[] 特殊字符分割后的char 数组  如 123-> #1#2#3#
     */
    private static char[] arrayIntervalSpecialChar(String sourceStr) {
        char[] sourceCharArray = sourceStr.toCharArray();
        char[] res = new char[sourceCharArray.length * 2 + 1];
        int indexOfSource = 0;
        for (int index = 0; index < res.length; index++) {
            if (index % 2 == 0) {
                res[index] = SPECIAL_CHAR;
            } else {
                res[index] = sourceCharArray[indexOfSource];
                indexOfSource++;
            }
        }
        return res;
    }

    public static int findLongestPalindromicSubLen(String str) {
        str = Optional.ofNullable(str)
                .orElseThrow(() -> new IllegalArgumentException("字符串不可以为null"));
        //被特殊字符分割后的字符数组
        char[] specialCharInterval = arrayIntervalSpecialChar(str);
        //如果长度小于2 返回长度 一个字符返回1， 空白串 null 返回0
        if (str.length() < 2) {
            return str.length();
        }
        //最长回文半径数组 记录index位置字符向两端扩展生成的最大回文子串的半径
        int[] maxRadiusLen = new int[specialCharInterval.length];
        //当前最长回文子串的最右位置
        int mostRightPosition = -1;
        //当前最长回文子串的中点
        int mostRightCenter = -1;
        int maxLenResult = Integer.MIN_VALUE;
        //循环遍历当前char数组
        for (int index = 0; index < specialCharInterval.length; index++) {
            int curLongest;
            //第一种情况 如果当前位置在mostRightPosition 右侧 那么进行暴力求解最长回文子串长度
            if (index >= mostRightPosition) {
                int tempRight = palindromeMostRight(specialCharInterval, index, specialCharInterval.length);
                curLongest = palindromeLenOf(specialCharInterval, index, tempRight);
                //当前最长 对于第一个a 是 1-0为1 表示 a自己回文 right=1 表示到b就不回文了
                //当前最长 对于第一个b 是 2-1 为1 表示 b向左右扩宽1 right=2 回文最长边界为2 表示到c就不回文了
                //你可能觉得这里  curLongest 错了 但是 别忘了我们字符串经过特殊处理 =>
                //abac=>#a#b#a#c# 对于b index=3 right=6 6-3=3 正好是 aba的长度呀！！！
                maxRadiusLen[index] = curLongest;
                if (mostRightPosition < tempRight) {
                    mostRightPosition = tempRight;
                    mostRightCenter = index;
                }
            } else { //第二种情况 index在mostRightPosition 内
                //index关于 当前最长回文串对称的位置
                int indexSymmetry = 2 * mostRightCenter - index;
                int mostLenPre = maxRadiusLen[indexSymmetry];
                int mostLeftPosition = 2 * mostRightCenter - mostRightPosition;
                //indexSymmetry 的最长回文子串的最左位于 mostLeftPosition 右侧
                if ((indexSymmetry - mostLenPre) > mostLeftPosition) {
                    curLongest = mostLenPre;
                } else if ((indexSymmetry - mostLenPre) < mostLeftPosition) {
                    //indexSymmetry 的最长回文子串最左位于 mostLeftPosition 的左侧
                    curLongest = mostLenPre;
                } else {
                    //indexSymmetry 的最长回文子串最左位于 mostLeftPosition 重合
                    //进行暴力求解
                    int tempRight = palindromeMostRight(specialCharInterval, mostRightPosition, specialCharInterval.length);
                    if (mostRightPosition < tempRight) {
                        mostRightPosition = tempRight;
                        mostRightCenter = index;
                    }
                    curLongest = palindromeLenOf(specialCharInterval,index,tempRight);
                }
                maxRadiusLen[index] = curLongest;
            }
            maxLenResult = Math.max(curLongest, maxLenResult);
        }
        return maxLenResult;
    }

    private static int palindromeMostRight(char[] charArray, int start, int end) {
        checkParamInRange(charArray, start, end);
        int left = start - 1;
        int right = start + 1;
        while (left >= 0 && right < end) {
            if (charArray[left] == charArray[right]) {
                left--;
                right++;
            } else {
                break;
            }
        }
        return right;
    }


    private static void checkParamInRange(char[] charArray, int start, int end) {
        if (charArray == null) {
            throw new IllegalArgumentException("字符数组不可以为null");
        }
        if (start < 0 || start > end || start > charArray.length) {
            throw new IllegalArgumentException("开始位置需要大于0小于字符数组长度并且小于end");
        }
        if (end > charArray.length) {
            throw new IllegalArgumentException("结束位置需要小于字符数组长度");
        }
    }

    private static int palindromeLenOf(char[] charArray, int center, int mostRight) {
        int left = 2 * center - mostRight ;
        if (charArray[Math.min(charArray.length-1,mostRight - 1)] == charArray[left]) {
            return mostRight - center;
        } else {
            return mostRight - center - 1;
        }
    }

    public static void main(String[] args) {
        String str = "eacbaccabcae";
//        String str = "abcbdkskdbcbaeabcbdkskdbcbae";
//        String str = "abcdedcbakabcdedcft";
        System.out.println(str.length());
//        System.out.println("cdedcbakabcdedc".length());
        int longestPalindromicSubLen = findLongestPalindromicSubLen(str);
        System.out.println(longestPalindromicSubLen);
//        String str = "#aa#b#ac#";
//        //          0123456
//        int right = palindromeMostRight(str.toCharArray(), 0, str.length());
//        System.out.println(right);
//        System.out.println(palindromeLenOf(str.toCharArray(), 0, right));
    }
}
